/* A program that simulates an viral infection of humans by Zombies in 
 * 2038. This is a modified version of the Game of Life, which 
 * calculates a given state of a 'colony' based on the prior state
 * of the colony and other specified rules.
 *
 * This modified version allows the user to use many threads and implements
 * concurrant programming.
 *
 * 4/23/13
 * Ben Marks, Gabe Ryan
 */


#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/time.h>
#include <errno.h>
#include <pthread.h>

#include <semaphore.h>


pthread_barrier_t barrier;
pthread_cond_t cond;
pthread_mutex_t mux;
sem_t proceed1;
sem_t proceed2;


int numReached;
int numThreads;

struct thread_args{
  unsigned char * board1;
  unsigned char * board2;
  int num_iters;
  int total_rows;
  int total_cols;
  int print;
  int verbose;
  int num_off;
  int num_per;
  int row_based;
  int tid;
  int (*waitFunc)( void );
};


// Function Declarations
void fillArray(unsigned char * array, int rows, int cols, unsigned char param);
void printArray(unsigned char * array, int rows, int cols); 
struct thread_args setParams(char * argv[]);
int getNewValue(unsigned char * old_grid, int row, int col, 
    int rows, int cols);
void * threadWork(struct thread_args * args);


int semWait() {
  int toRet = 0;
  int i = 0;
  if ( pthread_mutex_lock( &mux ) ) {
    perror("mutex_lock");
    exit(1);
  }
  numReached ++;

  if ( numReached == numThreads ) {
    for (i = 0; i < numThreads; i++) {
      sem_post(&proceed1);
    }
    toRet = PTHREAD_BARRIER_SERIAL_THREAD;
  }

  if ( pthread_mutex_unlock( &mux ) ) {
    perror("mutex unlock");
    exit(1);
  }

  sem_wait(&proceed1);
  
  if ( pthread_mutex_lock( &mux ) ) {
    perror("mutex_lock");
    exit(1);
  }
  numReached --;
  if ( numReached == 0 ) {
    for (i = 0; i < numThreads; i++) {
      sem_post(&proceed2);
    }
  }
  if ( pthread_mutex_unlock( &mux ) ) {
    perror("mutex unlock");
    exit(1);
  }

  sem_wait(&proceed2);

  return toRet;
}

int barrierWait() {
  
  return pthread_barrier_wait( &barrier );

}


int condWait() {
  int toRet = 0;
  if ( pthread_mutex_lock( &mux ) ) {
    perror("mutex_lock");
    exit(1);
  }
  numReached ++;
  if ( numReached == numThreads ) {
    numReached = 0;
    if ( pthread_cond_broadcast( &cond ) ) {
      perror("cond_broadcast");
      exit(1);
    }
    toRet = PTHREAD_BARRIER_SERIAL_THREAD;
  }
  else {
    pthread_cond_wait( &cond, &mux );
  }
  if (pthread_mutex_unlock( &mux ) ) {
    perror ("mutex unlock");
    exit(1);
  }
  return toRet;
}

/* Main function responsible for calling all other functions and 
 * executing simulation.
 *
 * Returns - 0 if successful; 1 if unsuccessful
 *
 * Inputs: argc - number of command line arguments typed
 *         argv[] - array of strings of those command line args
 *
 */
int main(int argc, char * argv[]){
 
  // Check for valid number of inputs
  if (argc != 7) {
    printf("\n\nSorry, I need 6 inputs.\n"
        "Usage: %s  <config file>  <print>  <ntids>  <partition> <verbose> <synch> \n"
        "<print>     : 0 - don't print each iteration\n"
        "              1 - print each iteration\n"
        "<ntids>     : enter number of threads to use in parallelization\n"
        "<partition> : 0 - partition work by rows\n"
        "              1 - partition work by columns\n"
        "<verbose>   : 0 - don't print data about work allocation\n"
        "              1 - do print data about work allocation\n"
	"<synch>     : 1 - Use barriers to synchronize\n"
	"              2 - Use condition variables to synchronize\n"
        "              3 - Use semaphores to synchronize\n",
        argv[0]);
    exit(1);
  }

  // Initialize simulation global variables, process file input,
  // and set up boards
  struct thread_args args = setParams(argv);
  int num_threads = args.tid;
  numThreads = num_threads;
  numReached = 0;
  int i;

  if (args.print) { 
  printf("\n\nWelcome to Humans vs. Zombies, and watch as the horror\n"
      "unfolds....\n\nThe Peaceful Start:\n");
  }
  // Set up timer stuff
  struct timeval start,end;
  gettimeofday(&start, NULL);

  // Initialize barrier with given number of threads
  if( pthread_barrier_init(&barrier, NULL, num_threads)) {
    perror("Error: pthread_barrier_init failed.\n");
    exit(1);
  }
  if ( pthread_cond_init( &cond, NULL ) ) {
    perror("cond init");
    exit(1);
  }
  if ( pthread_mutex_init ( &mux, NULL ) ) {
    perror("mutex init");
    exit(1);
  }

  if ( sem_init( &proceed1, 0, 0 ) ) {
    perror("sem init");
    exit(1);
  }

  if ( sem_init( &proceed2, 0, 0 ) ) {
    perror("sem init");
    exit(1);
  }



  // Initialize TID array
  
  struct thread_args tids[num_threads];
  for (i=0; i<num_threads; i++) {
    tids[i] = args;
    tids[i].tid = i;
  }

  // Keep an array of threads
  pthread_t threads[num_threads];

  // Initialize all threads
  for (i=0; i<num_threads; i++) {
    if (pthread_create(&threads[i], NULL, (void *) &threadWork,
          (void * ) &tids[i])) {      
      perror("Error: pthread_create failed.");
      exit(1);
    }
  }

  // Join all threads
  for (i=0; i<num_threads; i++) {
    if (pthread_join(threads[i], NULL)) {
      perror("Error: pthread_join failed.\n");
      exit(1);
    }
  }

  // Get ending time
  gettimeofday(&end, NULL);
  long time = (end.tv_sec*1000000 + end.tv_usec) -
    (start.tv_sec*1000000 + start.tv_usec);

  // Clean up barrier
  if (pthread_barrier_destroy(&barrier)) {
    perror("Error: pthread_barrier_destroy failed.\n");
  }
  pthread_mutex_destroy( &mux );
  pthread_cond_destroy( &cond );
  sem_destroy (&proceed1);
  sem_destroy (&proceed2);

  // Print results of simulation for batch analysis
  //printf("%d\t%d\t%d\t%ld\t", args.total_rows, args.total_cols, 
  //    num_threads, time);
 

  // Print results for readability
  printf("\nRows:\t %d \
      \nColumns:\t %d \
      \nThreads:\t %d \
      \nTime:\t %ld \t microseconds\n", args.total_rows, 
      args.total_cols, num_threads, time);

  free(args.board1);
  free(args.board2);
  return 0;
}


/*
 * Sets variables about the simulation state in a struct of variables
 * that is returned by value. Does all the necessary setup for
 * board by initailizing the virus cells, validating all input, etc.
 *
 * Returns the struct of all information regarding the simulation.
 */
struct thread_args setParams(char * argv[]) {
  // Declare local variables
  int num_coords;
  int i;
  struct thread_args args;
 
  // Open up the file
  FILE * infile = fopen(argv[1], "r");  
  if (!infile) { // Error opening file
    printf("Error opening file %s. \n\n",
        argv[1]);    
    exit(1);
  }

  // Read in lines from input file
  fscanf(infile, "%d", &args.total_rows);
  fscanf(infile, "%d", &args.total_cols);
  fscanf(infile, "%d", &args.num_iters);
  fscanf(infile, "%d", &num_coords);
  // Check for input errors
  if (!args.total_rows || !args.total_cols || !args.num_iters ||
      !num_coords){
    printf("Invalid file input.\n\n");
    fclose(infile);
    exit(1);
  }
  else if (args.total_rows < 1 || args.total_cols < 1 || 
      args.num_iters < 1 || num_coords < 0){
    printf("Invalid inputs for parameters in file.\n\n");
    fclose(infile);
    exit(1);
  }


  // Get large array for simulation
  args.board1 = 
    (unsigned char *)malloc(sizeof(char)*args.total_rows*args.total_cols);
  if (!args.board1) {
    perror("\nMalloc Error...\n\n");
    fclose(infile);
    exit(1);
  }
  args.board2 = 
    (unsigned char *)malloc(sizeof(char)*args.total_rows*args.total_cols);
  if (!args.board2) {
    perror("\nMalloc Error...\n\n");
    fclose(infile);
    exit(1);
  }

  // Initialize first board
  fillArray(args.board1, args.total_rows, args.total_cols, 1);
  
  // Set virus cells
  int row, col, num_read;
  for (i=0; i<num_coords; i++){
    // Try reading coordinates from file
    num_read = fscanf(infile, "%d %d", &row, &col);
    if (num_read != 2 || row < 0 || col < 0 || 
        row >= args.total_rows || col >= args.total_cols)
    { // Some error occured
      printf("Invalid coordinates in file.\n\n");
      free(args.board1);
      free(args.board2);
      fclose(infile);
      exit(1);
    }
    // Set cell to virus
    args.board1[(row*args.total_cols+col) % 
      (args.total_rows*args.total_cols)] = 2;
  }



  // Check valid inputs for show / not show
  args.print = atoi(argv[2]);
  if (args.print != 1 && args.print != 0) {
    printf("Invalid paramter for show. Should be 0 or 1!\n\n");
    fclose(infile);
    exit(1);
  }

  // Check valid inputs for partition
  args.row_based = ! atoi(argv[4]);
  if (args.row_based != 1 && args.row_based != 0) {
    printf("Invalid paramter for partition. Should be 0 or 1!\n\n");
    exit(1);
  }
  
  // Check valid inputs for number of threads
  int num_threads = atoi(argv[3]);
  if (num_threads < 1) {
    printf("Invalid paramter for num threads. Should be >= 1!\n\n");
    exit(1);
  }
  // Check that number of threads !> number rows/ cols
  if (args.row_based) {
    if (num_threads > args.total_rows) {
      num_threads = args.total_rows;
    }
  }
  else {
    if (num_threads > args.total_cols) {
      num_threads = args.total_cols;
    }
  }

  // Set division of work variables
  if (args.row_based) {
    args.num_per = args.total_rows / num_threads;
    args.num_off = args.total_rows % num_threads;
  }
  else {
    args.num_per = args.total_cols / num_threads;
    args.num_off = args.total_cols % num_threads;
  }


  // Check valid inputs for verbose
  args.verbose = atoi(argv[5]);
  if (args.verbose != 1 && args.verbose != 0) {
    printf("Invalid paramter for verbose. Should be 0 or 1!\n\n");
    exit(1);
  }
  fclose(infile);
  args.tid = num_threads;


  int function = atoi(argv[6]);
  if ( function < 1 || function > 3 ) {
    printf("Invalid parameter for function. Should be 1, 2, or 3!\n\n");
    exit(1);
  }
  if ( function == 1 ) {
    args.waitFunc = &barrierWait;
  }
  else if (function == 2 ) {
    args.waitFunc = &condWait;
  }
  else {
    args.waitFunc = &semWait;
  }

  return args;
}


/*
 * Function run by each thread. First determines the cells to update
 * based on the number of threads and partitioning choices. Then 
 * updates the cells and prints the results (if specified). 
 *
 * Actions between threads are synchronized with barriers to ensure 
 * correct results.
 */
void * threadWork(struct thread_args * args) {
  
  // Calculate rows and columns; get global simulation state
  int i, row, col, start_col, end_col, start_row, end_row, print;
  int tid = args->tid;

  // Determine partitioning based on number of threads
  if (args->row_based) {
    start_col = 0;
    end_col = args->total_cols;
  
    if (tid < args->num_off) {
      start_row = tid*(args->num_per+1);
      end_row = start_row+args->num_per+1;
    }
    else {
      start_row = args->num_off*(args->num_per+1) +
        (tid - args->num_off)*args->num_per;
      end_row = start_row + args->num_per;
    }
  }
  else {
    start_row = 0;
    end_row = args->total_rows;
  
    if (tid < args->num_off) {
      start_col = tid*(args->num_per+1);
      end_col = start_col+args->num_per+1;
    }
    else {
      start_col = args->num_off*(args->num_per+1) +
        (tid - args->num_off)*args->num_per;
      end_col = start_col + args->num_per;
    }
  }
  print = args->print;

  // Make a local copy of simulation conditions
  int verbose = args->verbose;
  int num_iters  = args->num_iters;
  unsigned char * board1 = args->board1;
  unsigned char * board2 = args->board2;
  int total_rows = args->total_rows;
  int total_cols = args->total_cols;

  int (*waitFunc)( void ) = args->waitFunc;

  // Print thread info
  if (verbose) {
    printf("tid  %d: rows:  %d: %d (%d)  cols: %d:%d (%d)\n",
        tid, start_row, end_row-1, end_row-start_row, 
        start_col, end_col-1, end_col-start_col);
  }

  // MAIN UPDATING LOOP: 

  // Update cells for each iteration
  for (i=0; i<num_iters; i++) {
    for (row = start_row; row < end_row; row++) {
      for (col = start_col; col < end_col; col++) {
        // Update that cell
        board2[row*total_cols+col] = 
          getNewValue(board1, row, col, total_rows, total_cols);
      }
    }
    // Swap boards
    unsigned char * tmp = board1;
    board1 = board2;
    board2 = tmp;

    // Wait for everybody to catch up
    int ret = (*waitFunc)() ;
    if (ret != 0 && ret != PTHREAD_BARRIER_SERIAL_THREAD) {
      perror("Error: wait failed.\n");
    }
    
    // Allow printing thread to print
    if (print) {
      if (ret == PTHREAD_BARRIER_SERIAL_THREAD) {
        printArray(board1, total_rows, total_cols);
      }   
      // Wait for printing thread
      ret = (*waitFunc)();
      if (ret != 0 && ret != PTHREAD_BARRIER_SERIAL_THREAD) {
        perror("Error: wait failed.\n");
      }
      
    }

  }
  // Must return     void *
  return NULL;
}







/* Prints out the current array to show status of zombie attack.
 *
 * Parameters - 
 * int * array - 2D array with cells that are live / dead/ infected
 *      0 - Dead Cell
 *      1 - Live Cell
 *      2 - Virus Cell
 *
 * int rows - number of rows in array
 * int cols - number of columns in array
 */

void printArray(unsigned char * array, int rows, int cols) {
  
  system("clear");
  printf("\n");

  int i, j;
  unsigned char value;
  for (i=0; i<rows; i++) {
    for (j=0; j<cols; j++) {
      value = array[i*cols + j];
      if (value == 0) {
        printf("- ");
      }
      else if (value == 1) {
        printf("@ "); 
      }
      else {
        printf("X ");
      }
    }
    printf("\n");
  }

  usleep(200000);

}


/* Fill in the 2D array with some value. Used for initializing 'colony'
 *
 * Parameters
 * int * array- 2D array to fill in
 * int rows - number of rows in array
 * int cols - number of columnss in array
 * int val - value to fill in array with
 */

void fillArray(unsigned char * array, int rows, int cols, unsigned char val) {
  int i, j;
  for(i=0; i<rows; i++){
    for(j=0; j<cols; j++){
      array[i*cols + j] = val;
    }
  }
}


/* Calculate the status of a cell after an iteration, based on its 
 * current status and its neighbors.
 *
 * Parameters -
 * int * old_grid - array that is getting updated
 * int row - cell row index to update
 * int col - cell column index to update
 * int rows - number of rows in old grid
 * int cols - number of cols in old grid
 *
 *
 * Returns  - new value of the cell
 *      0 - dead cell
 *      1 - live cell
 *      2 - virus cell
 *
 */

int getNewValue(unsigned char * old_grid, int row, int col,
    int rows, int cols) {
  int cur_row, cur_col, i, j, n0, n1, n2;
  n0 = n1 = n2 = 0;
  unsigned char tmp = 0;
  unsigned char current;
  for (i=-1; i<2; i++) {
    cur_row = (row+i+rows) % rows;
    for (j=-1; j<2; j++) {
      cur_col = (col+j+cols) % cols;
      tmp = old_grid[cur_row*cols+cur_col];
      if (tmp == 0) {
        n0+= 1;
      }
      else if (tmp == 1) {
        n1 += 1;
      }
      else {
        n2 += 1;
      }
    }
  }

 current = old_grid[row*cols+col];
 if (current == 0) {
   return (n1 > 1);
 }
 
 if (current == 1) {
   if (n2 > 5) {
     return 0;
   }
   if (n2 > 2) {
     return 2;
   }
   return 1;
 }

 if (n2 > 4) { // 4 neighbor virus cells
   return 0;
 }
 if (n1 == 8) {
   return 0;
 }
 return 2;

}


